/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._160;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._160
 * @ClassName: IntersectionTwoLinkedLists
 * @Author: linyaonan
 * @Date: 2019/11/7 11:29
 */
public class IntersectionTwoLinkedLists {

    /**
     * 解法1：使用哈希表进行辅助
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            } else {
                headB = headB.next;
            }
        }

        return null;
    }

    /**
     * 解法2：使用链表相交的规律
     * a1 -> a2 -> c1 -> c2 -> c3
     *
     * b1 -> b2 -> b3 -> c1 -> c2 -> c3
     *
     * 链表1遍历完成后再从链表2开始遍历，链表2也是同理可以组成如下：
     *
     * 链表1：a1 -> a2 -> c1 -> c2 -> c3 -> b1 -> b2 -> b3 -> c1 -> c2 -> c3
     *
     * 链表2：b1 -> b2 -> b3 -> c1 -> c2 -> c3 -> a1 -> a2 -> c1 -> c2 -> c3
     *
     * 两个链表同时向后遍历，遇到相等的时候则认为相交
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;

        while (p1 != p2) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }

        return p1;

    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        ListNode result;
        while (curA!=null) {
            while (curB!=null) {
                if (curA == curB) {
                    result = curA;
                    if (checkIsInter(curA, curB)) {
                        return result;
                    }
                }
                curB = curB.next;
            }
            curA = curA.next;
            curB = headB;
        }
        return null;
    }

    private boolean checkIsInter(ListNode nodeA, ListNode nodeB) {
        while (nodeA!=null) {
            if (nodeA != nodeB) {
                return false;
            } else {
                nodeA = nodeA.next;
                nodeB = nodeB.next;
            }
        }
        return true;
    }

}
